#include <iostream>
using namespace std;
#define max 100
class graph
{
public:
    int dot_num;
    char dot[max];
    bool tag[max];
    int side[max][max];
    int out_d[max], in_d[max];
    string answer;
    graph()
    {
        cout << "input the number of dot:";
        int n;
        cin >> n; //输入点的个数
        dot_num = n;
        for (int i = 0; i < n; i++) //加入点
        {
            char dian;
            cout << "the name of dot(char)" << i + 1 << ":";
            cin >> dian;
            answer += dian; //初始化answer
            dot[i] = dian;  //设置点
            out_d[i] = 0;   //出度设为0
            in_d[i] = 0;    //入度设为0
            tag[i] = 0;     //标志设为0
            for (int j = 0; j < n; j++)
                side[i][j] = 0;
        }
        cout << "input the side(input 0 to end):" << endl;
        string s;
        while (1) //加入边，格式：ab（为从点a到点b的边）
        {
            cin >> s;
            if (s == "0")
                break;
            for (int i = 0; i < n; i++)
            {
                if (s[0] == dot[i])
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (s[1] == dot[j])
                        {
                            side[i][j] = 1; //边设为1
                            out_d[i] = 1;   //出度设为0
                            in_d[j] = 1;    //入度设为1
                        }
                    }
                }
            }
        }
    }
    void set_tag_0();             //全部标志置为0
    void DFS(int pos);            //深度优先搜索
    bool order(int i, int j);     //判断拓扑排序是否符合顺序
    void topolgical_dfs(int pos); //拓扑排序专用DFS
    bool no_loop();               //判断有没有环
    void all_topolgical_sort();   //输出所有拓扑排序
};
void graph::set_tag_0()
{
    for (int i = 0; i < dot_num; i++)
        tag[i] = 0;
}
void graph::DFS(int pos) //从dot【pos】开始深度优先遍历
{
    tag[pos] = 1;
    for (int j = 0; j < dot_num; j++)
    {
        if (side[pos][j] == 1)
        {
            if (tag[j] == 0)
                DFS(j);
        }
    }
}
bool graph::no_loop()
{
    for (int i = 0; i < dot_num; i++) //每个点都找有没有环
    {
        set_tag_0();
        DFS(i); //对当前点进行DFS
        for (int j = 0; j < dot_num; j++)
        {
            if (side[j][i] == 1) //存在 j 点到 i 点的边
            {
                if (tag[j] == 1) //并且从 i 点可以访问到 j 点
                {
                    return 0;
                }
            }
        }
    }
    return 1;
}
bool graph::order(int i, int pos) //是否符合拓扑排序的顺序
{
    for (int j = 0; j < pos; j++) //对answer中顺序检查
    {
        for (int k = 0; k < dot_num; k++) //找到answer【j】对应的点的索引
        {
            if (answer[j] == dot[k])
            {
                if (side[i][k] == 1) //如果answer中出现不符合顺序的两个点，则返回0
                {
                    return 0;
                }
            }
        }
    }
    return 1;
}
void graph::topolgical_dfs(int pos) //第pos-1次递归，当pos+1=点数时，完成一条线路的深度搜索，及拓扑排序递归
{
    if (pos == dot_num)
    {
        cout << answer << endl;
    }
    else
    {
        for (int i = 0; i < dot_num; i++) //对每个符合要求的点，访问
        {
            if (tag[i] == 0 && order(i, pos)) //没被访问，并且该字母不在字符串中
            {
                tag[i] = 1;
                answer[pos] = dot[i];
                topolgical_dfs(pos + 1);
                tag[i] = 0; //可以回溯
            }
        }
    }
}
void graph::all_topolgical_sort()
{
    if (no_loop()) //不存在环，才开始找拓扑排序
    {
        set_tag_0();
        topolgical_dfs(0); //从0开始构造
    }
    else
        cout << "there is loop in this graph." << endl;
}
int main(void)
{
    graph mygraph;
    mygraph.all_topolgical_sort();

    system("pause");
    return 0;
}